package leetcode

//暴力法
func trap(height []int) int {
	res:=0
	for i:=1;i<len(height)-1;i++{
		maxLeft,maxRight:=0,0
		for j:=i-1;j>=0;j--{
			if height[j]>maxLeft{
				maxLeft=height[j]
			}
		}
		for k:=i+1;k<len(height);k++{
			if height[k]>maxRight{
				maxRight=height[k]
			}
		}
		tmp:=min(maxLeft,maxRight)
		if tmp>height[i]{
			res+=tmp-height[i]
		}
	}
	return res
}
//动态规划
func trapDP(height []int) int {
	n:=len(height)
	maxLeft:=make([]int,n)
	maxRight:=make([]int,n)

	maxLeft[0]=height[0]
	for i:=1;i<n;i++{
		maxLeft[i]=max(maxLeft[i-1],height[i])
	}

	maxRight[n-1]=height[n-1]
	for i:=n-2;i>=0;i--{
		maxRight[i]=max(maxRight[i+1],height[i])
	}

	res:=0
	for i:=0;i<n;i++{
		res+=min(maxLeft[i],maxRight[i])-height[i]
	}
	return res
}
//双指针法
func trapDI(height []int) int {
	maxLeft,maxRight:=0,0
	left,right:=0,len(height)-1
	res:=0
	for left<right{
		maxLeft=max(maxLeft,height[left])
		maxRight=max(maxRight,height[right])
		if maxLeft<maxRight{
			res+=maxLeft-height[left]
			left++
		}else {
			res+=maxRight-height[right]
			right--
		}
	}
	return res
}
//维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 height 中的元素递减。
func trapStack(height []int) int {
	res:=0
	stack:=[]int{}
	for i:=0;i<len(height);i++{
		//遇见非递减的情况，则弹出栈来计算这一段的容积
		for len(stack)>0&&height[i]>stack[len(stack)-1]{
			//弹出栈顶元素来计算高度差
			top:=stack[len(stack)-1]
			stack=stack[:len(stack)-1]
			//如果这个top是左侧起点，则不用计算
			if len(stack)<1{
				break
			}
			left:=stack[len(stack)-1]
			curHeight:=min(height[left],height[i])-height[top]
			curWidth:=i-left-1
			res+=curHeight*curWidth
		}
		stack=append(stack, i)
	}
	return res
}